|
Necklace splitting is a picturesque name given to several related problems in combinatorics and measure theory. Its name and solutions are due to mathematicians Noga Alon and Douglas B. West. Example of necklace splitting with ''k'' = 2 (i.e. two partners), and ''t'' = 2 (i.e. two types of beads, here 8 red and 6 green). A 2-split is shown. The basic setting involves a necklace with beads of different colors. The necklace should be divided between several partners, such that each partner receives the same amount of every color. Moreover, the number of ''cuts'' should be as small as possible (in order to waste as little as possible of the metal in the links between the beads). == Variants == The following variants of the problem have been solved in the original paper: 1. Discrete splitting:〔 The necklace has beads. The beads come in different colors. There are beads of each color , where is a positive integer. Partition the necklace into parts (not necessarily contiguous), each of which has exactly beads of color ''i''. Use at most cuts. Note that if the beads of each color are contiguous on the necklace, then at least cuts must be done inside each color, so is optimal. 2. Continuous splitting:〔 The necklace is the real interval . Each point of the interval is colored in one of different colors. For every color , the set of points colored by is Lebesgue-measurable and has length , where is a non-negative real number. Partition the interval to parts (not necessarily contiguous), such that in each part, the total length of color is exactly . Use at most cuts. 3. Measure splitting:〔 The necklace is a real interval. There are different measures on the interval, all absolutely continuous with respect to length. The measure of the entire necklace, according to measure , is . Partition the interval to parts (not necessarily contiguous), such that the measure of each part, according to measure , is exactly . Use at most cuts. This is a generalization of the Hobby–Rice theorem, and it is used to get an exact division of a cake. Each problem can be solved by the next problem: * Discrete splitting can be solved by continuous splitting, since a discrete necklace can be converted to a coloring of the real interval in which each interval of length 1 is colored by the color of the corresponding bead. In case the continuous splitting tries to cut inside beads, the cuts can be slid gradually such that they are made only between beads.〔 * Continuous splitting can be solved by measure splitting, since a coloring of an interval in colors can be converted to a set measures, such that measure measures the total length of color . The opposite is also true: measure splitting can be solved by continuous splitting, using a more sophisticated reduction.〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Necklace splitting problem」の詳細全文を読む スポンサード リンク
|